from typing import List


class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])

        def near(x, y):
            """计算相邻的座位"""
            res = []
            if x > 0 and y > 0:
                res.append((x - 1, y - 1))
            if x > 0 and y < n - 1:
                res.append((x - 1, y + 1))
            if y > 0:
                res.append((x, y - 1))
            if y < n - 1:
                res.append((x, y + 1))
            if x < m - 1 and y > 0:
                res.append((x + 1, y - 1))
            if x < m - 1 and y < n - 1:
                res.append((x + 1, y + 1))
            return res

        ans = 0

        # 找出必然无法作弊、且是否做人也不影响其他人的位置
        for i1 in range(m):
            for j1 in range(n):
                if seats[i1][j1] == ".":
                    for i2, j2 in near(i1, j1):
                        if seats[i2][j2] == ".":
                            break
                    else:
                        ans += 1
                        seats[i1][j1] = "#"

        # 寻找所有可以互相影响的座位区域
        visited = set()
        areas = []
        for i in range(m):
            for j in range(n):
                if seats[i][j] == ".":
                    if (i, j) not in visited:
                        now = {(i, j)}
                        queue = [(i, j)]
                        while queue:
                            i1, j1 = queue.pop()
                            for i2, j2 in near(i1, j1):
                                if seats[i2][j2] == "." and (i2, j2) not in now:
                                    now.add((i2, j2))
                                    queue.append((i2, j2))
                        areas.append(list(now))
                        visited |= now

        # 计算每一个区域的最优解
        for area in areas:
            area.sort()
            print(area)

            # 计算每一块区域每一行中奇数列和偶数列的情况
            min_i, max_i = area[0][0], area[-1][0]
            nums = [[0, 0] for _ in range(min_i, max_i + 1)]
            for i, j in area:
                if j % 2 == 0:
                    nums[i - min_i][0] += 1
                else:
                    nums[i - min_i][1] += 1
            size = len(nums)

            # print(nums)

            # 定义状态矩阵：dp[i][j]从第[i,j]行的最大座位数
            dp = [[0] * size for _ in range(size)]
            for l in range(0, size):
                if l == 0:  # 1行
                    for i in range(size):
                        dp[i][i] = max(nums[i])
                elif l == 1:  # 2行：只能取其中的所有奇数列或所有偶数列
                    for i in range(size - 1):
                        j = i + 1
                        dp[i][j] = max(nums[i][0] + nums[j][0], nums[i][1] + nums[j][1])
                else:  # 3行及以上
                    for i in range(size - l):
                        j = i + l
                        # 取所有技术列或所有偶数列
                        dp[i][j] = max(sum(nums[k][0] for k in range(i, i + l + 1)),
                                       sum(nums[k][1] for k in range(i, i + l + 1)))

                        # 取k之前最优解和k的最优解
                        for k in range(i + 1, j):
                            dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j])

            for row in dp:
                print(row)

            # 累加最优解
            ans += dp[0][size - 1]

        return ans


if __name__ == "__main__":
    # 4
    print(Solution().maxStudents(seats=[["#", ".", "#", "#", ".", "#"],
                                        [".", "#", "#", "#", "#", "."],
                                        ["#", ".", "#", "#", ".", "#"]]))

    # 3
    print(Solution().maxStudents(seats=[[".", "#"],
                                        ["#", "#"],
                                        ["#", "."],
                                        ["#", "#"],
                                        [".", "#"]]))

    # 10
    print(Solution().maxStudents(seats=[["#", ".", ".", ".", "#"],
                                        [".", "#", ".", "#", "."],
                                        [".", ".", "#", ".", "."],
                                        [".", "#", ".", "#", "."],
                                        ["#", ".", ".", ".", "#"]]))

    # 测试用例53/55 : 9
    print(Solution().maxStudents(seats=[["#", "#", "#", ".", "#"],
                                        [".", ".", "#", ".", "."],
                                        ["#", ".", "#", ".", "#"],
                                        [".", ".", ".", ".", "."],
                                        [".", ".", ".", "#", "."]]))

    # 测试用例54/55 : 7
    print(Solution().maxStudents(seats=[["#", ".", "#", ".", "."],
                                        [".", "#", "#", "#", "#"],
                                        ["#", ".", ".", "#", "#"],
                                        ["#", ".", "#", ".", "."],
                                        ["#", ".", "#", "#", "."]]))
